class Solution {
public:
    int trap(vector<int>& height) {
        int n =height.size();
        stack<int>st;
        int nums=0;
        for(int i=0;i<n;++i){
            while(!st.empty()&&height[i]>height[st.top()]){
                int topIdx=st.top();
                st.pop();
                if(st.empty()){
                    break;
                }
                int l = st.top();
                int currWigth = i-l-1;
                int currHeight = min(height[l],height[i])-height[topIdx];
                nums += currWigth * currHeight;
            }
            st.push(i);
        }
        return nums;
    }
};
